0098. 验证二叉搜索树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归（上下界约束）

1. 📝 题目描述

• leetcode

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 严格小于 当前节点的数。
• 节点的右子树只包含 严格大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

---

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5，但是右子节点的值是 4。

---

提示：

• 树中节点数目范围在[1, 10^4] 内
• -2^31 <= Node.val <= 2^31 - 1

2. 🎯 s.1 - 递归（上下界约束）

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool validate(struct TreeNode* root, long lo, long hi) {
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return validate(root->left, lo, root->val) &&
           validate(root->right, root->val, hi);
}

bool isValidBST(struct TreeNode* root) {
    return validate(root, LONG_MIN, LONG_MAX);
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  const validate = (node, lo, hi) => {
    if (!node) return true
    if (node.val <= lo || node.val >= hi) return false
    return (
      validate(node.left, lo, node.val) && validate(node.right, node.val, hi)
    )
  }
  return validate(root, -Infinity, Infinity)
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node: Optional[TreeNode], lo: float, hi: float) -> bool:
            if not node: return True
            if node.val <= lo or node.val >= hi: return False
            return validate(node.left, lo, node.val) and \
                   validate(node.right, node.val, hi)
        return validate(root, float('-inf'), float('inf'))

• 时间复杂度：$O(n)$，其中 n 是树的节点数
• 空间复杂度：$O(n)$，递归栈的深度

算法思路：

• BST 的每个节点必须满足一个开区间约束 (lo, hi)
• 根节点的约束为 (-∞, +∞)
• 访问左子树时，上界缩小为当前节点值；访问右子树时，下界增大为当前节点值
• 若节点值不在 (lo, hi) 内，则返回 false